Some encryption protocols for electronic messages are based on modular mathematics, such as the Diffie-Hellman protocol and the Rivest-Shamir-Adleman (RSA) protocol. As an example of modular math, consider the expression X mod M=Z, where X is the operand, M is the modulus, and Z is the remainder. The value for the remainder, Z, is the same as the remainder from integer division of the operand, X, by the modulus, M. As a numerical example, consider 27 mod 10=7. The remainder, 7, is what is left after the operand 27 is divided by the modulus 10. The remainder 7 may also be referred to as the modular reduction of 27 modulo 10.
Modular arithmetic includes a variety of modular operations, including but not limited to, modular addition, modular subtraction, modular multiplication, modular division, and modular exponentiation. For example, XY mod M=Z is an example of modular multiplication in which Z is the modular reduction of the result of multiplying X by Y. As another example, XY mod M=Z is an example of modular exponentiation in which Z is the modular reduction of the result of raising X to the power Y.
Many encryption protocols rely on numerical “keys” that are used to encrypt and decrypt messages. Some protocols use private keys that are kept secret except from the parties exchanging the encrypted messages, while other protocols use a combination of private and public keys in which the public keys are freely distributed to the public at large while the private keys are kept secret.
Generally, the longer the key size used in a particular encryption protocol, the better the level of security that can be achieved. However, some encryption protocols involve modular operations, such as modular multiplication and modular exponentiation, which are computationally intensive, particularly for large operands that are associated with using longer keys. For example, for 2048 bit keys, a typical hardware implementation of the RSA protocol involves millions of logic gates and very high clock frequencies, which makes such hardware implementations impractical for widespread use. Therefore, hardware implementations of the RSA and other encryption protocols are generally limited to shorter keys to reduce computational requirements, but such shorter keys provide less security than longer keys.
One approach for performing modular operations for large operands is based on Montgomery's method, which is a modular operation algorithm where one modular reduction is performed at each iteration of the modular operation by a shift instead of a division. For example, given two operands, X and Y, and a modulus, M, the modular multiplication operation for computing the result, Z, of XY mod M based on Montgomery's method may be found by evaluating the expressions:S=XY Q=M′S mod W Z=(S+QM)/W where                W=2N         W≧4M        M′ is chosen such that M′ M=−1 mod W        
Using Montgomery's method in a hardware encryption device can reduce the complexity of the device. However, a drawback of this approach is that the result, Z, is not the exact result desired for XY mod M; rather, the result, Z, is a scaled result. In order to efficiently scale the result (i.e. reduce the scaling operation to a bit shift in binary numerical calculations), W must be chosen to be a power of two (i.e., N must be an integer), which limits the possible values of W for a given modulus, M. In addition, the approach presented above requires three sequential multiplication operations with very large operands (X and Y, represented in binary form, may have more than 1024 bits each, producing multiplication result with 2048 or more bits) which are very time consuming operation on a general purpose digital computer systems.
Based on the foregoing, it is desirable to provide improved techniques for encryption. It is also desirable to have improved techniques for implementations of encryption protocols that achieve acceptable performance for longer keys, in a hardware device that has a practical gate structure.